#include "common.h"

string w;
int len;
bool ans = false;
int arr[10][10];
int n, m;
int arr1[4][2] = { {1,0}, {-1,0}, {0,1},{0,-1} };

void dfs(vector<vector<char>>& board, int x, int y, int pos)
{
	if (ans) return;
	for (int i = 0; i < 4; i++)
	{
		int xx = x + arr1[i][0];
		int yy = y + arr1[i][1];
		if (xx >= 0 && xx < n && yy >= 0 && yy < m)
		{
			if (arr[xx][yy] == 0)
			{
				if (board[xx][yy] == w[pos])
				{
					arr[xx][yy] = 1;
					if (pos == len - 1)
					{
						ans = true;
						return;
					}
					dfs(board, xx, yy, pos + 1);
					arr[xx][yy] = 0;
				}
			}
		}
	}
}

bool exist(vector<vector<char>>& board, string word)
{
	w = word;
	len = w.size();
	n = board.size();
	m = board[0].size();
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (board[i][j] == word[0])
			{
				if (len == 1) return true;
				arr[i][j] = 1;
				dfs(board, i, j, 1);
				if (ans) return true;
				arr[i][j] = 0;
			}
		}
	}
	return false;
}